package com.example.leetcode;


import java.util.Arrays;

public class Sort {
    // 选择排序：找到当前基地pos，然后和与后面数据做比较，如果后面数据小于基地数据pos，
    // 交换，最后比较i=pos是否再同一个位置，不同交换，两次for循环 需要交换
    public static void selectSort(int[] nums){
        if (nums==null||nums.length==0){
            return;
        }

        for (int i=0;i<nums.length;i++){
            int pos=i;
            //j必须等于1+1！！
            for (int j=i+1;j<nums.length;j++){
                if(nums[j]<nums[pos]){
                    pos=j;
                }
            }
            if (i!=pos){
                int temp=nums[i];
                nums[i]=nums[pos];
                nums[pos]=temp;
            }
        }

    }
    //插入排序，将当前数据的下一个数据做为插入数据insert，比较后面一条数据和插入数据大小，
    // 如果大于插入数据，将后面这个数据前移，并且以此比较（j--），最后将插入数据赋给j+1
    //一次for选择一次while
    private static void insertSort(int[] nums){
        if (nums==null||nums.length==0){
            return;
        }
        for (int i=0;i<nums.length;i++){
            int insert=nums[i];
            int j=i-1;
            while (j>=0&&nums[j]>insert){
                nums[j+1]=nums[j];
                j--;
            }
            nums[j+1]=insert;
        }
    }

    //快速排序 需要递归，先比较开始数据和结束数据，找到基地数据pivot；先和左边比较如果左边数据小于基地数据右移，
    // 然后右边比较，如果右边数据比基地数据大，左移，然后再交换，再递归，三个while
    private static void quickSort(int[] nums){
        sort(nums,0,nums.length-1);
    }

    private static void sort(int[] nums,int start,int end){
        if (start>=end){
            return;
        }
        int pivot=nums[start];
        int left=start;
        int right=end;
        while (left<=right){
            while ((left<=right&&nums[left]<pivot)){
                left++;
            }
            while ((left<=right&&nums[right]>pivot)){
                right--;
            }
            if (left<=right){
                int temp=nums[right];
                nums[right]=nums[left];
                nums[left]=temp;
                left++;
                right--;
            }
        }
        sort(nums,start,right);
        sort(nums,left,end);

    }
    // 冒泡排序 每次和自己前一个数据比较，后面数据小交换，有几个数据循环遍历几次
    public static void doubleSort(int [] nums){
        if (nums==null||nums.length==0)
        {return;
        }
        for (int i=0;i<nums.length;i++){
            for (int j=1;j<nums.length;j++){
                //和自己上个数据比较
                if (nums[j-1]>nums[j]){
                    int temp = nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1]=temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums={2,5,3,8,6};
        doubleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}